package 链表.删除链表的倒数的第n个节点;

/**
 * 快慢指针
 * 定义块指针先走倒数的n步
 * 在块指针和慢指针一起走
 * 快指针走完后慢指针的下一个节点就是倒数第n个节点
 * 利用前置节点就可以删除了
 *
 *
 * */

class Solution1 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 删除节点slow的下一个节点
        ListNode prev = null;
        while(fast != null){
            // 慢指针的前节点，后面用于删除节点
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        prev.next = slow.next;
        slow.next = null;
        return dummy.next;
    }
}